package 一些算法竞赛测试题;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: a
 * Date: 2022-09-29
 * Time: 23:54
 */

/*
使用贪心算法解决多机调度问题
某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中
断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的最短时间
 */
public class Demo6 {
    private static int findMax(int[] machines){
        int len = machines.length;
        int res = machines[0];
        for(int i = 1; i < len; i++){
            res = Math.max(res, machines[i]);
        }
        return res;
    }

    private static int greedStrategy(int[] works, int[] machines){
        int n = works.length;
        int m = machines.length;
        if(n <= m){
            return works[n - 1];
        }else{
            //找到最先结束的机器分配新的任务
            for(int i = n - 1; i >= 0; i--){
                int finish = 0;
                int machinesTime = machines[finish];
                for(int j = 1; j < m; j++){
                    if(machines[j] < machinesTime){
                        finish = j;
                        machinesTime = machines[j];
                    }
                }
                machines[finish] += works[i];
            }
        }
        return findMax(machines);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] works = new int[n];
        int[] machines = new int[m];
        for(int i = 0; i < n; i++){
            works[i] = scanner.nextInt();
        }
        Arrays.sort(works);
        System.out.println(greedStrategy(works, machines));
    }
}
